
/*************
author:: libo
license:: MIT
*****************/
#include<Mesh/_Func_.h>
#include<Mesh/libcell_iterator.h>
#define iterator_v lib_cell_iterator_vertices
#define iterator_f lib_cell_iterator_faces
#define iterator_c lib_cell_iterator_cells
#define iterator_edge lib_cell_iterator_edge

#define quote lib_cell_quote
template_v* Mesh_get_vertexp(struct Mesh *m,int i)
{
    return (template_v*)(m->vertices->find(m->vertices,i));
}
template_c*  Mesh_get_cellp(struct Mesh*m,int i)
{
    return (template_c*)(m->cells->find(m->cells,i)); 
}
template_f* Mesh_get_facep(struct Mesh*m,int i)
{
    return (template_f*)(m->faces->find(m->faces,i));
}
template_hf* Mesh_get_halffacep(struct Mesh*m,int i)
{
    return (template_hf*)(m->halffaces->find(m->halffaces,i));
}
template_v Mesh_get_vertex(struct Mesh* own,int id)
{

    template_v *v=Mesh_get_vertexp(own,id);
    if(v!=NULL)
    {
        return *v;
    }
    template_v v1;
    Vertex_init_(&v1);
    return v1;
 
}
template_c Mesh_get_cell(struct Mesh* own,int id)
{

    template_c* c=Mesh_get_cellp(own,id);
    if(c!=NULL)
    {
        return *c;
    }
    template_c c1;
    Cell_init_(&c1);
    return c1;

}
template_f Mesh_get_face(struct Mesh*own,int id)
{

    template_f *f=Mesh_get_facep(own,id);
    if(f!=NULL)
    {
        return *f;
    } 
    template_f f1;
    Face_init_(&f1);
    return f1;
}
template_hf Mesh_get_halfface(struct Mesh*own,int id)
{
    template_hf* hf=Mesh_get_halffacep(own,id);
    if(hf!=NULL)
    {
        return *hf;
    }
    template_hf hf1;
    HalfFace_init_(&hf1);
    return hf1;

}
template_f* Mesh_get_facev(struct Mesh*own,template_v** temp_v,int size)
{
    
    Node* node=temp_v[0]->faces;
    bool b=false;
    while(node!=NULL)
    {   b=true;
        for(int i=1;i<size;i++)
        {
            if(node_find(temp_v[i]->faces,node->value)==NULL)
            {
                b=false;
                break;
            }
        }
        if(b)
        {
            break;
        }
        node=(Node*)(node->Next);
    }

    if(b)
    {
        return (template_f*)(node->value);
    }

    return NULL;
}
template_c* Mesh_get_cellv(struct Mesh*own,template_v** temp_v,int size)
{
    Node* node=temp_v[0]->cells;
    bool b=false;
    while(node!=NULL)
    {
        b=true;
        for(int i=1;i<size;i++)
        {
            if(node_find(temp_v[i]->cells,node->value)==NULL)
            {
                b=false;
                break;
            }
        
        }
        if(b)
        {
            break; 
        }
        node=(Node*)node->Next;
    
    }
    if(b)
    {
        return (template_c*)(node->value);
    
    }
    return NULL;

}
template_c* Mesh_get_cellf(struct Mesh* own,template_f** temp_f,int size)
{
    bool b=false;
    int i=0;
    for(i=0;i<2;i++)
    {   if(temp_f[0]->halffaces[i]->cell==NULL)
        {
            //b=false;
            continue;
        
        }
        b=true;
        for(int j=1;j<size;j++)
        {
            if(temp_f[j]->halffaces[0]->cell==temp_f[0]->halffaces[i]->cell||temp_f[j]->halffaces[1]->cell==temp_f[0]->halffaces[i]->cell)
            {
                continue;
            }
            else
            {
                b=false;
                break;
            } 
        }
        if(b)
        {
        break;
        }
    
    
    }
    if(b)
    {
        return (template_c*)temp_f[0]->halffaces[i]->cell;
    }
    return NULL;


}

int Mesh_num_c(struct Mesh* own)
{
    return own->cells->size;
    //return own->cells.size();
}
int Mesh_num_f(struct Mesh* own)
{
    return own->faces->size;
    //return own->faces.size();
}
int Mesh_num_v(struct Mesh* own)
{
    return own->vertices->size;
	//return own->vertices.size();
}
int Mesh_num_hf(struct Mesh* own)
{

    return own->halffaces->size;
    //return own->halffaces.size();
}
template_v* Mesh_create_vertex(struct Mesh* own)
{
    template_v* v=(template_v*)malloc(sizeof(template_v));

    Vertex_init_(v);
    v->id=own->vertex_id++;
    //own->vertices[v->id]=v;
    own->vertices->insert(own->vertices,v->id,v);
    return v;
}
template_v* Mesh_create_vertexv(struct Mesh*own,double* p,int size)
{

    template_v*v= Mesh_create_vertex(own);
    v->point_size=size;
    v->point=(double*)malloc(sizeof(double)*size);
    for(int i=0;i<size;i++)
    {
        v->point[i]=p[i];
    
    }
    return v;
}
template_f * Mesh_create_face(struct Mesh* own)
{
    template_f* f=(template_f*)malloc(sizeof(template_f));
    Face_init_(f);
    f->halffaces[0]->cell=NULL;f->halffaces[1]->cell=NULL;
    f->id=own->face_id++;
    
    //own->faces[f->id]=f;
    own->faces->insert(own->faces,f->id,f);
    return f;

}
template_c* Mesh_create_cell(struct Mesh* own)
{
    template_c *c=(template_c*)malloc(sizeof(template_c));

    Cell_init_(c);
    c->id=own->cell_id++;
    
    //own->cells[c->id]=c;
    own->cells->insert(own->cells,c->id,c);

    return c;
}
//如果返回NULL,意味创建失败
template_hf * Mesh_create_halfface(struct Mesh* own,template_f* f,template_v** temp_v,int size)
{
    if(f==NULL)
    {
        return 0;
    }
    if(f->halffaces[0]->cell!=NULL&&f->halffaces[1]->cell!=NULL)
    {
        return NULL;
    }


    template_hf *hf=NULL;
    if(f->halffaces[0]->vertices==NULL)
    {
        hf=f->halffaces[0];
    }
    else if(f->halffaces[1]->vertices==NULL)
    {

        hf=f->halffaces[1];
    }
    else
    {
        if(f->halffaces[0]->cell==NULL)
        {
            hf=f->halffaces[0];
        }
        else if(f->halffaces[1]->cell==NULL)
        {
            hf=f->halffaces[1];
        }
        else
        {

            printf("流形的网格拓扑错误\n"); 
            for(int i=0;i<size;i++)
            {
                printf("%d ",temp_v[i]->id);
            }
            printf("\n");
            return NULL;
        }
    }
    hf->id=own->halfface_id++;
 
    //own->halffaces[hf->id]=hf;
    own->halffaces->insert(own->halffaces,hf->id,hf);

    if(hf->vertices==NULL)
    {
        hf->vertices=(template_v**)malloc(sizeof(template_v*)*size);
    }
    for(int i=0;i<size;i++)
    {
        hf->vertices[i]=temp_v[i];
    }
    hf->vertices_size=size;
    

    return hf;
}
//以下程序表明点到face的遍历没有不能保证顺(逆)时针(当cell是曲面)
template_f* Mesh_create_facev(struct Mesh*own,template_v** temp_v,int size)
{
	template_f*f=Mesh_get_facev(own,temp_v,size);
	if(f==NULL)
	{
	    f=Mesh_create_face(own);
	}
	else
	{
	    return f;
	}
	f->vertices_size=size;
	f->vertices=(template_v**)malloc(sizeof(template_v*)*size);
    for(int i=0;i<size;i++)
    {

        f->vertices[i]=temp_v[i];
        temp_v[i]->faces=node_overlying(temp_v[i]->faces,(void*)f);

    }
    return f;
}
//要判断是否已经创建相应的cell
template_c* Mesh_create_cellf(struct Mesh* own,template_hf**temp_hf,int size)
{
    if(temp_hf[0]->cell!=NULL)
    {
        //exist cell
        return temp_hf[0]->cell;
    }
    template_c* c=Mesh_create_cell(own);
    
    Node* node=NULL,*node_v=NULL;
    for(int i=0;i<size;i++)
    {
        temp_hf[i]->cell=c;
        node=node_overlying(node,(void*)temp_hf[i]);
        for(int j=0;j<temp_hf[i]->vertices_size;j++)
        {
            if(node_find(node_v,temp_hf[i]->vertices[j])==NULL)
            {
                node_v=node_overlying(node_v,temp_hf[i]->vertices[j]); 
            
            } 
        } 
    }
    c->halffaces=node;

    Node* temp_nodev=node_v;
    node_v=node_reverse(node_v);
    int le=node_size(node_v);
    c->vertices=(template_v**)malloc(sizeof(template_v*)*le);
    c->vertices_size=le;
    int i=0;
    while(node_v!=NULL)
    {       c->vertices[i]=(template_v*)(node_v->value);

        
        ((template_v*)(node_v->value))->cells=node_overlying(((template_v*)(node_v->value))->cells,(void*)c);
        node_v=(Node*)(node_v->Prev);
        i++;
    }
    free_node(temp_nodev);
    return c;
}
//应该写 Mesh_get_cellv，并用在下面判断(但速度会变慢)
//以下程序也不能保证点到cell的遍历是顺(逆)时针(当cell表示面时)
//创建单形使用的函数
//如果返回NULL意味创建失败
template_c* Mesh_create_cellv(struct Mesh* own,template_v** temp_v,int size)
{
    template_c* ccc= Mesh_get_cellv(own,temp_v,size);
    if(ccc!=NULL)
    {
        return ccc;
    }

    template_hf** hfs=(template_hf**)malloc(sizeof(template_hf*)*size);

    template_v** temp_v1=(template_v**)malloc(sizeof(template_v*)*(size-1));
    for(int i=0;i<size;i++)
    {
        int temp_i=0;
        for(int j=0;j<size;j++)
        {
            if(j!=i)
            {

                temp_v1[temp_i]=temp_v[j];
                temp_i++;
            }
        }
        if((size-i-1)%2==0)
        {}
        else if(size>2)
        {
            template_v* vv=temp_v1[0];
            temp_v1[0]=temp_v1[1];
            temp_v1[1]=vv;
        }
        template_f* f=Mesh_create_facev(own,temp_v1,size-1);
        hfs[i]=Mesh_create_halfface(own,f,temp_v1,size-1);
        if(hfs[i]==NULL)
        {
           free(temp_v1);free(hfs);
           return NULL; 
        }
    }


    template_c* c=Mesh_create_cell(own);
    c->vertices=(template_v**)malloc(sizeof(template_v*)*size);
    c->vertices_size=size;


    for(int i=0;i<size;i++)
    {
        c->vertices[i]=temp_v[i];

        temp_v[i]->cells=node_overlying(temp_v[i]->cells,(void*)c);
//#ifdef SIMPLEX_REQUIRE   
     
        hfs[i]->cell=c;
        c->halffaces=node_overlying(c->halffaces,(void*)(hfs[i]));
//#endif
    }
    free(hfs);
    free(temp_v1);
    return c;
}
int Mesh_delete_vertex(struct Mesh*own,template_v v_,int burning)
{
    template_v*v=NULL;
  
    Int_RB_Tree_Node* it=int_rb_tree_find(own->vertices,v_.id);
    if(it==NULL)
    {
        return 0;
    }
    else
    {
        v=(template_v*)(it->data);
        int_rb_tree_delete_node(own->vertices,it);
    }


    template_c*c;
	Node* node=node_copy(v->cells),*node1=NULL,*node2=NULL;
	node1=node;
	while(node1!=NULL)
	{   
        node2=(Node*)(node1->Next);
	    c=(template_c*)(node1->value);
	    Mesh_delete_cell(own,*c,true);
	    node1=node2;
	
    }
	free_node(node);


//#ifndef MANIFOLD_REQUIRE
    if(own->manifold_require==0)
    {
        node=node_copy(v->faces);
        template_f*f;
        node1=node;
        while(node1!=NULL)
        {   
            node2=(Node*)(node1->Next);
            f=(template_f*)(node1->value);
            Mesh_delete_face(own,*f,true);
            node1=node2;
        }
        free_node(node);
    }
	

//#endif

    if(burning)
    {
 	    free_Vertex(v);       
	}

    return 1;
}
int Mesh_delete_halfface(struct Mesh*own,template_hf f_,int burning)
{
     template_hf* hf=NULL;


    Int_RB_Tree_Node* it=int_rb_tree_find(own->halffaces,f_.id);
    if(it!=NULL)
    {
        hf=(template_hf*)(it->data);

    } 
    else
    {
        return false;
    }

    if(hf->cell!=NULL)
    {
        Mesh_delete_cell(own,*((template_c*)(hf->cell)),burning);
        hf->cell=NULL;
    }
//#ifndef MANIFOLD_REQUIRE
    if(own->manifold_require==0)
    {
        if(hf->vertices!=NULL)
        {
            free(hf->vertices);
            hf->vertices=NULL;
        }
        hf->vertices_size=0;
        //own->halffaces.erase(it);
        int_rb_tree_delete_node(own->halffaces,it);
    }
    
//#endif
     
    return true;
}
int Mesh_delete_face(struct Mesh*own,template_f f_,int burning)
{
    template_f*f=NULL;
   
    Int_RB_Tree_Node* it=int_rb_tree_find(own->faces,f_.id);
    if(it!=NULL)
    {
        f=(template_f*)(it->data);
    }
    else
    {
        return false;
    }
    for(int i=0;i<2;i++)
    {
        if(f->halffaces[i]->cell!=NULL)
        {
            Mesh_delete_cell(own,*(f->halffaces[i]->cell),burning);
        }
    }
 
//#ifndef MANIFOLD_REQUIRE
    if(own->manifold_require==0)
    {
        int_rb_tree_delete_node(own->faces,it);
        for(int i=0;i<f->vertices_size;i++)
        {
            Vertex_remove_f((template_v*)f->vertices[i],f);
        }
        if(burning)
        {
            free_Face(f);
        }
    }
   
//#endif
    return true;
}
int Mesh_delete_cell(struct Mesh* own,template_c c_,int burning)
{
    template_c* c;
    Int_RB_Tree_Node* it=int_rb_tree_find(own->cells,c_.id);
    if(it!=NULL)
    {
        c=(template_c*)(it->data);
        int_rb_tree_delete_node(own->cells,it);
    }
    else
    {
        return false;
    }

    //handle with face
    template_f*f;
    Node* node=c->halffaces,*node1=NULL;
    while(node!=NULL)
    {
        node1=(Node*)(node->Next);
      //  f=(template_f*)(((template_hf*)node->value)->face);
        //face要甩掉cell
        //Face_remove_c(f,c);
        Halfface_remove_c((template_hf*)(node->value),c);

        // auto hfit=own->halffaces.find(((template_hf*)(node->value))->id);
        // if(hfit!=own->halffaces.end())
        // {
        //     own->halffaces.erase(hfit);
        // }
        own->halffaces->erase(own->halffaces,((template_hf*)(node->value))->id); 
        node=node1;
    }
    template_v*v;
    for(int i=0;i<c->vertices_size;i++)
    {
        v=(template_v*)c->vertices[i];
        Vertex_remove_c(v,c);
    }
//#ifdef MANIFOLD_REQUIRE
    if(own->manifold_require==1)
    {
        Node* node_f=c->halffaces;
        while(node_f!=NULL)
        {
            f=(template_f*)((template_hf*)(node_f->value))->face;
            if(f->halffaces[0]->cell==NULL&&f->halffaces[1]->cell==NULL)
            {
                for(int i=0;i<f->vertices_size;i++)
                {
                    Vertex_remove_f((template_v*)f->vertices[i],f);

                }
            
                own->halffaces->erase(own->halffaces,f->halffaces[0]->id);
                own->halffaces->erase(own->halffaces,f->halffaces[1]->id);
                own->faces->erase(own->faces,f->id);
          

                if(burning)
                {
                    free_Face(f);
                }
            }
            node_f=(Node*)(node_f->Next);

        }
    //
    //如果要严格删除孤立点，则取消注释一下代码
/*    for(int i=0;i<c->vertices_size;i++)
    {
        v=(template_v*)(c->vertices[i]);
        if(v->cells==NULL)
        {
            auto vit=own->vertices.find(v->id);
            if(vit!=own->vertices.end())
            {
                own->vertices.erase(vit);
            }
            free_Vertex(v);
        }

    }
  */  
    }
  
//#endif
 
    if(burning)
    {
        free_Cell(c);

    }
    return true;
}
int Mesh_face_is_boundary(struct Mesh* own,template_f *f)
{

    return Mesh_nface_is_boundary(own,*f);
}
int Mesh_nface_is_boundary(struct Mesh* own,template_f f)
{
    if(f.halffaces[0]->cell==NULL||f.halffaces[1]->cell==NULL)
    {   return true;}
    return false;
}
//孤立点也是边界点
int Mesh_vertex_is_boundary(struct Mesh* own,template_v v)
{

    Node* node=v.faces;
    if(node==NULL)
    {
        return true;
    }
    while(node!=NULL)
    {
        if(Mesh_nface_is_boundary(own,*((template_f*)(node->value))))
        {   return true;}
        node=(Node*)(node->Next);
    }
    return false;
}
int Mesh_face_is_in_cell(struct Mesh* own,template_f*f ,template_c* c)
{
    for(Node* nit=c->halffaces;nit!=NULL;nit=(Node*)(nit->Next))
    {
        template_hf* hf=(template_hf*)(nit->value);
        if(hf->face==f)
        {
            return true;
        }
    }
    return false;
}
int Mesh_vertex_is_in_cell(struct Mesh* own,template_v*v,template_c*c)
{
    for(int i=0;i<c->vertices_size;i++)
    {
        if(c->vertices[i]==v)
        {
            return true;
        }
    }
    return false;
}
int Mesh_vertex_is_in_face(struct Mesh* own,template_v*v,template_f*f)
{
    for(int i=0;i<f->vertices_size;i++)
    {
        if(f->vertices[i]==v)
        {
            return true;
        }
    }
    return false;
}
//
//给它一个初始面，他会返回boundary的node链.这种寻找边界的方式.
//返回半边
//用红黑树RB_Tree做标记，代替prop
//
Node* Mesh_node_of_boundary_face(struct Mesh* own,template_f *f_)
{

    Int_RB_Tree* tree=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    int_rb_tree_init(tree); 

    // RB_Tree* tree=(RB_Tree*)malloc(sizeof(RB_Tree));
    // rb_tree_init_int(tree);
    // RB_int rbt,*rbt1=NULL;
    if(f_==NULL)
    {
        int_rb_tree_free(tree);
        //rb_tree_free(tree);
        return NULL;
    }
    Node* node=NULL,*node3=NULL;
    template_f *f;

    template_hf* hf;
    f=(template_f*)(own->faces->find(own->faces,f_->id));
    if(f==NULL)
    {
        return NULL;
    }
    // auto it=own->faces.find(f_->id);
    // if(it==own->faces.end())
    // {   printf("没找到\n");
    //     return NULL;
    // }
    // else
    // {
    //     f=it->second;
    // }
    if(!Mesh_nface_is_boundary(own,*f_))
    {return NULL;}
    else
    { 
        node=node_overlying(node,(void*)f);
        
        if(f->halffaces[1]->cell==NULL)
        {
            hf=f->halffaces[1];
            node3=node_overlying(node3,(void*)hf);
        }
        if(f->halffaces[0]->cell==NULL)
        {
            hf=f->halffaces[0];
            node3=node_overlying(node3,(void*)hf);
        }

    }
   // 深度优先的遍历
//   printf("shendu\n");
   //int* temp_faces=(int*)malloc(sizeof(int));
   //*temp_faces=1;
    template_v *v;
    Node* node2;
    while(node!=NULL)
    {   
        push:
        f=(template_f*)(node->value);
//        printf("f : %d\n",f->id);
        if(f->halffaces[0]->cell!=NULL)
        {
            hf=f->halffaces[0];
        }
        else
        {
            hf=f->halffaces[1];
        }
        //rbt.key=f->id;
        tree->insert(tree,f->id,NULL);
        //tree->insert(tree,&rbt);
        //f->prop=(void*)temp_faces;
        for(int i=0;i<hf->vertices_size;i++)
        {
            v=(template_v*)(hf->vertices[i]);
            node2=v->faces;

            while(node2!=NULL)
            {
                if(Mesh_nface_is_boundary(own,*((template_f*)(node2->value))))
                {
                   
                    // rbt.key=((template_f*)(node2->value))->id;
                    // rbt1=(RB_int*)tree->find(tree,&rbt);
                    void * var=tree->find(tree,((template_f*)(node2->value))->id);
                    //if(rbt1==NULL)
                    if(var==NULL)
                    {
                        node=node_overlying(node,node2->value);
                        void* temp_value=NULL;
                        if(((template_f*)node2->value)->halffaces[0]->cell==NULL)
                        {
                           temp_value=(void*)(((template_f*)node2->value)->halffaces[0]);
                            node3=node_overlying(node3,temp_value);
                        }
                        else if(((template_f*)node2->value)->halffaces[1]->cell==NULL)
                        {

                            temp_value=(void*)(((template_f*)node2->value)->halffaces[1]);
                             node3=node_overlying(node3,temp_value);
                        }
                       
                        goto push;
                    
                    }
                }
                node2=(Node*)node2->Next;

            }
        }
    
        Node *node1=node;
        node=(Node*)node->Next;
        
        free(node1);
        node1=NULL;
    }
    //free(temp_faces);
    int_rb_tree_free(tree);
    return node3;
}
static Node* Mesh_one_dim_boundary(struct Mesh* own)
{
    Node* node=NULL;
    // for(auto it=own->faces.begin();it!=own->faces.end();it++)
    // {
    //     if(it->second->halffaces[0]->cell==NULL)
    //     {
    //         node=node_overlying(node,it->second->halffaces[0]);
    //     }
    //     else if(it->second->halffaces[1]->cell==NULL)
    //     {
    //         node=node_overlying(node,it->second->halffaces[1]);
    //     }
    // }
    for(auto it=Mesh_f_beginn(own);it!=Mesh_f_endn(own);it++)
    {
        if(((template_f*)(quote(it)))->halffaces[0]->cell==NULL)
        {
            node=node_overlying(node,((template_f*)(quote(it)))->halffaces[0]);
        }
        else if(((template_f*)(quote(it)))->halffaces[1]->cell==NULL)
        {
            node=node_overlying(node,((template_f*)(quote(it)))->halffaces[1]);
        }
    }


    return node;
}
//
void Mesh_external_cell_init_(struct Mesh* own)
{
    
    free_node(own->external_cell.halffaces);
    own->external_cell.halffaces=NULL;
//#ifdef MANIFOLD_REQUIRE
    if(own->dimension==1&&own->manifold_require==1)
    {
          own->external_cell.halffaces= Mesh_one_dim_boundary(own);
//            printf("external_cell size:%d\n",node_size(own->external_cell.halffaces));

          return;
    }
//#endif
    for(auto it=Mesh_f_beginn(own);it!=Mesh_f_endn(own);it++)
    {
        if(Mesh_nface_is_boundary(own,*((template_f*)(quote(it)))))
        {
            own->external_cell.halffaces=Mesh_node_of_boundary_face(own,((template_f*)(quote(it))));
            break;
        }

    }
    // for(auto it=own->faces.begin();it!=own->faces.end();it++)
    // {   
    //     if(Mesh_nface_is_boundary(own,*(it->second)))
    //     {
    //         own->external_cell.halffaces=Mesh_node_of_boundary_face(own,it->second);
    //         break;
    //     }
    // }
    template_hf* hf1,*hf2;
    Node* node=own->external_cell.halffaces;
  //  printf("external_cell size:%d\n",node_size(node));
    if(node==NULL)
    {
        return;
    }
    //reset_f_prop(own);
    while(node!=NULL)
    {

        hf1=(template_hf*)(node->value);
        if(hf1->vertices!=NULL)
        {
		    free(hf1->vertices);
		    hf1->vertices=NULL;
	    }
	
         hf2=Mesh_s_opposite_halfface(hf1);
         hf1->vertices=(template_v**)malloc(sizeof(template_v*)*hf2->vertices_size);

         hf1->vertices_size=hf2->vertices_size;
         for(int i=0;i<hf2->vertices_size;i++)
         {
              hf1->vertices[i]=hf2->vertices[i];
//              printf("external cell h_f id:%d ",((template_v*)(hf1->vertices[i]))->id);
         }
        if(hf1->vertices_size>=2)
        {
              template_v * temp=hf1->vertices[0];
              hf1->vertices[0]=hf1->vertices[1];
              hf1->vertices[1]=temp;
         }
         node=(Node*)(node->Next);
    }
}
template_hf Mesh_opposite_halfface(template_hf hf)
{
    template_f*f=(template_f*)hf.face;
    if(f->halffaces[0]->cell==hf.cell)
    {
        return *(f->halffaces[1]);
    }
    else
    {
        return *(f->halffaces[0]);

    }
}
template_hf* Mesh_s_opposite_halfface(template_hf*hf)
{
    template_f*f=(template_f*)(hf->face);
     if(f->halffaces[0]==hf)
     {
        return f->halffaces[1];
     }
     else if(f->halffaces[1]==hf)
     {
        return f->halffaces[0];
     }
     return NULL;
}   
//需要修改的函数
Node* Mesh_non_manifold_vertices(struct Mesh* own)
{
    Node* re=NULL;
    for(auto iter=Mesh_v_beginn(own);iter!=Mesh_v_endn(own);iter++)
    {
        if(((template_v*)(quote(iter)))->cells==NULL)
        {
            re=node_overlying(re,quote(iter));
        }
    }
    // for(auto iter=own->vertices.begin();iter!=own->vertices.end();iter++)
    // {
    //     if(iter->second->cells==NULL)
    //     {
    //         re=node_overlying(re,iter->second);
        
    //     } 
    // }
    return re;
}
int Mesh_two_cell_is_connected(struct Mesh* own,template_c* c1,template_c* c2)
{
    bool re=false;
    if(c1==NULL||c2==NULL)
    {
        return re;
    }

    for(auto hfit=Mesh_chf_begin(own,*c1);hfit!=Mesh_chf_end(own,*c1);hfit++)
    {
        if(Mesh_s_opposite_halfface(quote(hfit))->cell==c2)
        {
            return true;
        }
    }
    return re;

}
int Mesh_is_manifold_vertices(struct Mesh*own,template_v*v)
{
    if(v->cells==NULL)
    {
        return false;
    } 
    Node* ncs=node_copy(v->cells);
    Node* n1=ncs,*n2=(Node*)(n1->Next);

    n1->Next=NULL;
    if(n2!=NULL)
    {
        n2->Prev=NULL;
    }
    int flag=0;
    do{
        flag=0;
        for(Node* nit=n2;nit!=NULL;nit=(Node*)(nit->Next))
        {
            for(Node* nnit=n1;nnit!=NULL;nnit=(Node*)(nnit->Next))
            {
                
                if(Mesh_two_cell_is_connected(own,(template_c*)(nit->value),(template_c*)(nnit->value)))
                {
                    flag=1;
                    n1=node_overlying(n1,nit->value);
                    n2=node_delete_value(n2,nit->value);
                    break;
                }

                
            }
            if(flag==1)
            {
                break;
            }

        } 

    }while(flag==1);
    if(n2==NULL)
    {
        free_node(n1);
        return true;
    }
    else
    {

        free_node(n1);
        return false;
    }

    //Node* re[2]={NULL,NULL};
   // Node* n1=v->cells,*n2=(Node*)(n1->Next);


    return true;
}
void Mesh_reset_c_prop(struct Mesh* mesh)
{
    // for(auto cit=mesh->cells.begin();cit!=mesh->cells.end();cit++)
    // {
    // cit->second->prop=NULL;
    // }
    for(auto cit=Mesh_c_beginn(mesh);cit!=Mesh_c_endn(mesh);cit++)
    {
        ((template_c*)(quote(cit)))->prop=NULL;
    }
}
void Mesh_reset_v_prop(struct Mesh* mesh)
{
    // for(auto vit=mesh->vertices.begin();vit!=mesh->vertices.end();vit++)
    // {
    //     vit->second->prop=NULL;     
    // }
    for(auto vit=Mesh_v_beginn(mesh);vit!=Mesh_v_endn(mesh);vit++)
    {
        ((template_v*)(quote(vit)))->prop=NULL;
    } 

}
void Mesh_reset_hf_prop(struct Mesh* mesh)
{
    // for(auto hfit=mesh->halffaces.begin();hfit!=mesh->halffaces.end();hfit++)
    // {
    //     hfit->second->prop=NULL;   
    // }
    for(auto hfit=Mesh_hf_beginn(mesh);hfit!=Mesh_hf_endn(mesh);hfit++)
    {
        ((template_hf*)(quote(hfit)))->prop=NULL;
    }
}
void Mesh_reset_f_prop(struct Mesh* mesh)
{
    // for(auto fit=mesh->faces.begin();fit!=mesh->faces.end();fit++)
    // {
    //     fit->second->prop=NULL; 
    // }
    for(auto fit=Mesh_f_beginn(mesh);fit!=Mesh_f_endn(mesh);fit++)
    {
        ((template_f*)(quote(fit)))->prop=NULL;
    }
}


iterator_v Mesh_v_beginn(struct Mesh * own)
{
    iterator_v it;
    iterator_v_init(&it);
    it.it=own->vertices->begin(own->vertices);
    return it;
}
iterator_v Mesh_v_endn(struct Mesh*own)
{
   iterator_v it;
   iterator_v_init(&it);
   return it; 
}

iterator_hf Mesh_hf_beginn(struct  Mesh*own)
{
    iterator_hf it;
    iterator_hf_init(&it);
    it.it=own->halffaces->begin(own->halffaces);
    return it;
}
iterator_hf Mesh_hf_endn(struct  Mesh*own)
{
    iterator_hf it;
    iterator_hf_init(&it);
    return it;
}

iterator_f Mesh_f_beginn(struct  Mesh*own)
{
    iterator_f it;
    iterator_f_init(&it);
    it.it=own->faces->begin(own->faces);
    return it;
}
iterator_f Mesh_f_endn(struct  Mesh*own)
{
    iterator_f it;
    iterator_f_init(&it);
    return it;
}

iterator_c Mesh_c_beginn(struct Mesh*own)
{
    iterator_c it;
    iterator_c_init(&it);
    it.it=own->cells->begin(own->cells);
    return it;
}
iterator_c Mesh_c_endn(struct Mesh*own)
{
     iterator_c it;
    iterator_c_init(&it);
    return it;
}

iterator_v Mesh_fv_begin(struct Mesh* own,template_f f_)
{

    iterator_v it;
    iterator_v_init(&it);
    it.value=f_.vertices;
    return it;

}

iterator_v Mesh_fv_end(struct Mesh* own,template_f f_)
{
    iterator_v it;
    iterator_v_init(&it);
    it.value=f_.vertices;
    it.i=f_.vertices_size;
    return it;

}
iterator_v Mesh_hfv_begin(struct Mesh* own,template_hf hf)
{
    iterator_v it;
    iterator_v_init(&it);
    it.value=hf.vertices;
    return it;

}
iterator_v Mesh_hfv_end(struct Mesh* own,template_hf hf)
{
    iterator_v it;
    iterator_v_init(&it);
    it.value=hf.vertices;
    it.i=hf.vertices_size;

    return it;
}
iterator_v Mesh_cv_begin(struct Mesh* own,template_c c)
{
    iterator_v it;
    iterator_v_init(&it);
    it.value=c.vertices;
    return it;
}
iterator_v Mesh_cv_end(struct Mesh* own,template_c c)
{
    iterator_v it;
    iterator_v_init(&it);
    it.value=c.vertices;
    it.i=c.vertices_size;
    return it;
}


iterator_f Mesh_vf_begin(struct Mesh* own,template_v v)
{
    iterator_f iff;
    iterator_f_init(&iff);
    if(v.faces==NULL)
    {
        return iff;
    }
    //***********
    //可以通过node->traits记录起点增加速度
    //***************
    if(v.faces->traits==NULL)
    {
        v.faces->traits=(void*)(node_reverse(v.faces));
    }
    iff.node=*((Node*)(v.faces->traits));
    return iff;

}
iterator_f Mesh_vf_end(struct Mesh* own,template_v v)
{
    iterator_f iff;
    iterator_f_init(&iff);
    return iff;

}
iterator_hf Mesh_chf_begin(struct Mesh* own, template_c c)
{

    iterator_hf iff;
    iterator_hf_init(&iff);
    if(c.halffaces==NULL)
    {
        return iff;
    }
    if(c.halffaces->traits==NULL)
    {
        c.halffaces->traits=(void*)(node_reverse(c.halffaces));
    }
    iff.node=*((Node*)(c.halffaces->traits));

    return iff;
}
iterator_hf Mesh_chf_end(struct Mesh* own,template_c c)
{
    iterator_hf iff;
    iterator_hf_init(&iff);
    return iff;

}
iterator_c Mesh_vc_begin(struct Mesh* own,template_v v)
{
    iterator_c it;
    iterator_c_init(&it);
    if(v.cells==NULL)
    {
        return it;
    }
    it.node=*(v.cells);
    return it;

}
iterator_c Mesh_vc_end(struct Mesh* own,template_v v)
{

    iterator_c it;
    iterator_c_init(&it);
    return it;
}
iterator_edge Mesh_edge_begin(struct Mesh*own,template_v v,template_f f  )
{
   
    iterator_edge ie;
    iterator_edge_init(&ie); 
    for(Node* nit=v.faces;nit!=NULL;nit=(Node*)(nit->Next))
    {
        template_f* f1=(template_f*)(nit->value);
        if(f1->id==f.id)
        {
            ie.f=f1;
            break;
        }
    }
    for(int i=0;i<f.vertices_size;i++)
    {
        if(f.vertices[i]->id==v.id)
        {
            ie.v=f.vertices[i];
            break;
        }
    }
    ie.mark=ie.f;
  
    return ie;
}
Node* Mesh_vv_begin(struct Mesh* own,template_v v)
{
    if(own->simplex!=1)
    {
        printf("is not simplex\n");
        return NULL;
    }
    Node* node=NULL;
    for(iterator_f fit=Mesh_vf_begin(own,v);fit!=Mesh_vf_end(own,v);fit++)
    {
        for(auto vit=Mesh_fv_begin(own,*fit);vit!=Mesh_fv_end(own,*fit);vit++)
        {
            if((*vit).id!=v.id)
            {

                if(node_find(node,(void*)quote(vit))==NULL)
                {
                    node=node_overlying(node,(void*)quote(vit));
                }
            }
        }
    }
    return node;


}
Node* Mesh_vv_end(struct Mesh* own,template_v  vv)
{

    return NULL;
}
void Mesh_printself(struct Mesh* own)
{
    printf("****************************\n\n");
    for(auto it=Mesh_v_beginn(own);it!=Mesh_v_endn(own);it++)
    {
        printf("id :%d \n",((template_v*)(quote(it)))->id);
        for(int j=0;j<((template_v*)(quote(it)))->point_size;j++)
        {
            printf("%lf  ",((template_v*)(quote(it)))->point[j]); 
        }
        printf("\n");
    } 

    printf("faces\n");
    for(auto it=Mesh_f_beginn(own);it!=Mesh_f_endn(own);it++)
    {
       printf("id:%d\n",((template_f*)(quote(it)))->id);
       if(((template_f*)(quote(it)))->prop!=NULL)
       {
            printf("prop ");
       }
       for(int j=0;j<((template_f*)(quote(it)))->vertices_size;j++)
       {
           printf("id :%d  ",((template_v*)(((template_f*)(quote(it)))->vertices[j]))->id);
       
       }
       printf("\n");
    }
    printf("cell\n");
    for(auto it=Mesh_c_beginn(own);it!=Mesh_c_endn(own);it++)
    {
        printf("cell id:%d\n",((template_c*)(quote(it)))->id);
        for(int j=0;j<((template_c*)(quote(it)))->vertices_size;j++)
        {
            printf("id %d  ",((template_v*)(((template_c*)(quote(it)))->vertices[j]))->id);
        }
        printf("\n");
    }
    // for(auto it=own->vertices.begin();it!=own->vertices.end();it++)
    // {
    //     printf("id :%d \n",it->second->id);
    //     for(int j=0;j<it->second->point_size;j++)
    //     {
    //         printf("%lf  ",it->second->point[j]); 
    //     }
    //     printf("\n");
    // }
    // printf("faces\n");
    // for(auto it=own->faces.begin();it!=own->faces.end();it++)
    // {
    //    printf("id:%d\n",it->second->id);
    //    if(it->second->prop!=NULL)
    //    {
    //         printf("prop ");
    //    }
    //    for(int j=0;j<it->second->vertices_size;j++)
    //    {
    //        printf("id :%d  ",((template_v*)(it->second->vertices[j]))->id);
       
    //    }
    //    printf("\n");
    // }
    // printf("cell\n");
    // for(auto it=own->cells.begin();it!=own->cells.end();it++)
    // {
    //     printf("cell id:%d\n",it->second->id);
    //     for(int j=0;j<it->second->vertices_size;j++)
    //     {
    //         printf("id %d  ",((template_v*)(it->second->vertices[j]))->id);
    //     }
    //     printf("\n");
    // }
 printf("****************************\n\n");

}
Node* Mesh_intersection_two_faces(struct Mesh*own,template_f*f0,template_f*f1)
{
    Node * node=NULL;
    int flag=1;
    for(int i=0;i<f0->vertices_size;i++)
    {
        flag=1;
        for(int j=0;j<f1->vertices_size;j++)
        {
            if((f0->vertices[i])==f1->vertices[j])
            {
                flag=0;
                break;
            } 
        }
        if(flag==0)
        {
            Node* node=node_overlying(node,f0->vertices[i]);
        }
    }
    return node;
}
void Mesh_free(struct Mesh* own)
{
    if(own->external_cell.halffaces!=NULL)
    {
        free_node(own->external_cell.halffaces);
        own->external_cell.halffaces=NULL;
    }
    for(auto iter=Mesh_c_beginn(own);iter!=Mesh_c_endn(own);iter++)
    {

        free_Cell((template_c*)(quote(iter)));
    } 

    for(auto iter=Mesh_f_beginn(own);iter!=Mesh_f_endn(own);iter++)
    {
        free_Face((template_f*)(quote(iter)));
    } 
    for(auto iter=Mesh_v_beginn(own);iter!=Mesh_v_endn(own);iter++)
    {
        free_Vertex((template_v*)(quote(iter)));
    }

    int_rb_tree_free(own->cells);
    int_rb_tree_free(own->faces);
    int_rb_tree_free(own->halffaces);
    int_rb_tree_free(own->vertices);
    own->cells=NULL;own->faces=NULL;own->halffaces=NULL;own->vertices=NULL;
    own->cell_id=0;own->vertex_id=0;own->face_id=0;own->halfface_id=0;

    
    // for(auto iter=own->cells.begin();iter!=own->cells.end();iter++)
    // {
    //     free_Cell(iter->second);
    // }
    // for(auto iter=own->faces.begin();iter!=own->faces.end();iter++)
    // {
    //     free_Face(iter->second);
    // } 
    // for(auto iter=own->vertices.begin();iter!=own->vertices.end();iter++)
    // {
    //     free_Vertex(iter->second);
    // }    
    // own->cells.clear();
    // own->faces.clear();
    // own->halffaces.clear();
    // own->vertices.clear(); 
}


void Mesh_init(struct Mesh* own)
{
    
    own->faces=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    own->cells=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    own->halffaces=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));
    own->vertices=(Int_RB_Tree*)malloc(sizeof(Int_RB_Tree));


    int_rb_tree_init((own->cells));
    int_rb_tree_init((own->faces));
    int_rb_tree_init((own->vertices));
    int_rb_tree_init((own->halffaces));
    //own->cells.insert(&(own->cells),9,NULL); 
    // own->vertices=(RB_Tree*)malloc(sizeof(RB_Tree));
    // rb_tree_init_int(own->vertices);
    // own->halffaces=(RB_Tree*)malloc(sizeof(RB_Tree));
    // rb_tree_init_int(own->halffaces);
    // own->faces=(RB_Tree*)malloc(sizeof(RB_Tree));
    // rb_tree_init_int(own->faces);
    // own->cells=(RB_Tree*)malloc(sizeof(RB_Tree));
    // rb_tree_init_int(own->cells);





    Cell_init_(&(own->external_cell));
    own->cell_id=0;own->vertex_id=0;own->face_id=0;own->halfface_id=0;
    own->get_vertexp=Mesh_get_vertexp;


    own->get_facep=Mesh_get_facep;
    own->get_halffacep=Mesh_get_halffacep;
    own->get_cellp=Mesh_get_cellp; 
    own->get_vertex=Mesh_get_vertex;
    own->get_cell=Mesh_get_cell;
    own->get_face=Mesh_get_face;
    own->get_halfface=Mesh_get_halfface;
    own->get_facev=Mesh_get_facev;
    own->get_cellv=Mesh_get_cellv;
    own->get_cellf=Mesh_get_cellf;
    own->num_v=Mesh_num_v;
    own->num_c=Mesh_num_c;
    own->num_f=Mesh_num_f;
    own->num_hf=Mesh_num_hf;
    own->create_vertex=Mesh_create_vertex;
    own->create_vertexv=Mesh_create_vertexv;
    own->create_cell=Mesh_create_cell;
    own->create_face=Mesh_create_face;
    own->create_cellv=Mesh_create_cellv;
    own->create_cellf=Mesh_create_cellf;
    own->create_facev=Mesh_create_facev;
    own->create_halfface=Mesh_create_halfface;
    own->delete_cell=Mesh_delete_cell;
    own->delete_vertex=Mesh_delete_vertex;
    own->delete_face=Mesh_delete_face;
    own->delete_halfface=Mesh_delete_halfface;
    own->vertex_is_boundary=Mesh_vertex_is_boundary;
    own->face_is_boundary=Mesh_nface_is_boundary;
    own->face_is_in_cell=Mesh_face_is_in_cell;
    own->vertex_is_in_cell=Mesh_vertex_is_in_cell;
    own->vertex_is_in_face=Mesh_vertex_is_in_face;

    own->node_of_boundary_face=Mesh_node_of_boundary_face;
    own->external_cell_init_=Mesh_external_cell_init_;
    own->opposite_halfface=Mesh_opposite_halfface;
    own->s_opposite_halfface=Mesh_s_opposite_halfface;


    own->v_begin=Mesh_v_beginn;
    own->v_end=Mesh_v_endn;
    own->f_begin=Mesh_f_beginn;
    own->f_end=Mesh_f_endn;
    own->hf_begin=Mesh_hf_beginn;
    own->hf_end=Mesh_hf_endn;
    own->c_begin=Mesh_c_beginn;
    own->c_end=Mesh_c_endn;

    own->cv_begin=Mesh_cv_begin;
    own->cv_end=Mesh_cv_end;
    own->fv_begin=Mesh_fv_begin;
    own->fv_end=Mesh_fv_end;
    own->hfv_begin=Mesh_hfv_begin;
    own->hfv_end=Mesh_hfv_end;
    own->vc_begin=Mesh_vc_begin;
    own->vc_end=Mesh_vc_end;
    own->vf_begin=Mesh_vf_begin;
    own->vf_end=Mesh_vf_end;
    own->chf_begin=Mesh_chf_begin;
    own->chf_end=Mesh_chf_end;
    own->vv_begin=Mesh_vv_begin;
    own->vv_end=Mesh_vv_end;
    own->edge_begin=Mesh_edge_begin;
    own->intersection_two_faces=Mesh_intersection_two_faces;
    own->non_manifold_vertices=Mesh_non_manifold_vertices;
    own->printself=Mesh_printself;
   
    own->reset_f_prop=Mesh_reset_f_prop;
    own->reset_hf_prop=Mesh_reset_hf_prop;
    own->reset_c_prop=Mesh_reset_c_prop;
    own->reset_v_prop=Mesh_reset_v_prop;




    own->simplex=1;
    own->dimension=-1; 
    own->manifold_require=1;

    own->prop=NULL;
    meshT_init(&(own->traits));
}

